﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.hot100
{
    public class Solution1143
    {
        public int LongestCommonSubsequence(string text1, string text2)
        {

            int m = text1.Length;
            int n = text2.Length;

            int[][] dp = new int[m + 1][];//以这个字符结尾的，是不是子序列

            for (int i = 0; i <= m; i++)
            {


                dp[i] = new int[n + 1];
            }
            int res = 0;

            for (int i = 1; i <= m; i++)
            {


                for (int j = 1; j <= n; j++)
                {

                    if (text1[i - 1] == text2[j - 1])
                    {
                        Console.WriteLine(dp[i][j]);
                        dp[i][j] = dp[i - 1][j - 1] + 1;

                    }
                    else
                    {
                        dp[i][j] = Math.Max(dp[i][j - 1], dp[i - 1][j]);
                    }
                    res = Math.Max(dp[i][j], res);
                }

            }

            return res;





        }
    }

    class Program1143
    {


        static void Main1143(string[] args)
        {
            Solution1143 solution = new Solution1143();
           string text1 = "abcde", text2 = "ace";
          int res=  solution.LongestCommonSubsequence(text1, text2);
            Console.WriteLine(res);

        }
    }
}
